import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-02-22
 * Time: 19:29
 */
class MyArrayList<E>{
    private Object[] elementData; // 数组
    private int usedSize; //代表数组的有效数据个数

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //无参的构造方法
    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //有参的构造方法（传入容量）
    public MyArrayList(int capacity){
        //如果给定的容量大于0，则创建一个给定容量大小的数组
        if(capacity>0){
            this.elementData = new Object[capacity];
        }else if(capacity==0){
            this.elementData = new Object[0];
        }else {
            throw new IllegalArgumentException("初始化的容量不能为负数"); //如果给定容量小于0，则抛出异常
        }
    }

    /**
     * 添加元素,相当于存放在数组的最后的位置
     * @param e 数据
     * @return
     */
    public boolean add(E e){
        //确定一个真正的容量【把检查顺序表和判断满并扩容放在了一起】
        ensureCapacityInternal(usedSize+1);
        elementData[usedSize] = e;
        usedSize++;
        return true;
    }

    public void ensureCapacityInternal(int minCapacity){
        //计算出需要的容量
        int capacity = calculaterCapacity(elementData,minCapacity);
        //拿着计算出的容量进行判断（空的或者满了就进行扩容）
        ensureExplicitCapacity(capacity);
    }

    private void ensureExplicitCapacity(int minCapacity){
       //如果进不去if语句，表示数组还没有放满
        //如果当前容量大于数组的长度，就进入if语句，然后进行扩容
        if(minCapacity - elementData.length >0){
            //扩容
            grow(minCapacity);
        }
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5倍扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //说明所需要的容量非常大
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError(); //越界异常
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

//计算是否分配容量
private static int calculaterCapacity(Object[] elementData,int minCapacity){
    //判断 elementData 是否分配过大小
    if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
        //如果没有分配容量，就返回10 （DEFAULTCAPACITY_EMPTY_ELEMENTDATA 值为0）
        return Math.max(10,minCapacity);
    }
    //分配过容量，就返回usedSize+1后的值
    return minCapacity;
}

    /**
     * 给index位置添加元素
     * @param index
     * @param e
     */
    public void addIndex(int index,E e){
        //检查index是否合法
        rangeCheckForAdd(index);
        //确定真正的容量
        ensureCapacityInternal(usedSize+1);
        //挪数据
        copy(index,e);
        usedSize++;
    }
    //拷贝的过程
    private void copy(int index , E e){
        for (int i = usedSize-1; i >=index ; i--) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = e;
    }
    //判断index是否合法
    private void rangeCheckForAdd(int index){
        if(index<0 || index>usedSize){
            throw new IndexOutOfBoundsException("index位置不合法，不能插入！");
        }
    }
}

public class TestDemo1 {
    public static void main(String[] args) {
    MyArrayList<String> list = new MyArrayList<>();
        list.add("ab");
        list.add("abc");
        list.add("abcd");
        list.add("abcde");
        list.addIndex(0,"789");
        System.out.println("df ");
    }
}
